def merge_sort(arr):
    if len(arr)<=1:
        return arr
    mid=len(arr)//2
    l=merge_sort(arr[:mid])
    r=merge_sort(arr[mid:])
    return merge(l,r)


def merge(left, right):
    ans=[]
    i=0
    j=0
    while i<len(left) and j<len(right):
        if left[i]<right[j]:
            ans.append(left[i])
            i+=1
        else:
            ans.append(right[j])
            j+=1
    ans+=left[i:]
    ans+=right[j:]
    return ans


# 🎉 示例
arr = [5, 2, 9, 1, 6, 3]
sorted_arr = merge_sort(arr)
print("喵呜~归并排序结果:", sorted_arr)
